package leetcodecompetition.S108;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-07-08-22:54
 * @Description: 1.0
 */
public class T6923 {
    public int minimumBeautifulSubstrings(String s) {
        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        int res=dp(s, 0, dp);
        return res==16?-1:res;
    }

    public int dp(String s, int a, int[] dp) {
//        System.out.println("aaa" + a);
        if (a >= s.length()) return 0;
        if (dp[a] != -1) {
            return dp[a];
        }
        int res = 16;
        for (int j = 0; j < 7; j++) {
            String s0 = Integer.toBinaryString((int) Math.pow(5, j));
            if (s.startsWith(s0, a)) {
//                System.out.println(s0 + "  " + a);
                res = Math.min(res, 1+dp(s, a + s0.length(), dp));
            }
        }
        dp[a] = res;
        return res;
    }
}
